#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=55,M=2505;
int n,m,dp[N][M],jc[N],pre[N][M],mo,T,ny;
int mod(int a)
{
	if(a>=mo) a-=mo;
	return a;
}
int ksm(int a,int b,int c)
{
	int ans=1;
	while(b>0)
	{
		if(b%2==1) ans=(ll)ans*a%c;
		a=(ll)a*a%c;
		b/=2;
	}
	return ans;
}
int main()
{
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
    scanf("%d%d",&mo,&T);
    int ny=ksm(2,mo-2,mo);
    while(T--)
    {
    	scanf("%d%d",&n,&m);
    	memset(dp,0,sizeof(dp));
    	memset(pre,0,sizeof(pre));
		dp[0][0]=1;
		for(int a=0;a<=n*m;a++) pre[0][a]=1;
        for(int a=1;a<=n;a++)
        {
         	for(int b=0;b<=n*m;b++)
          	{
          		dp[a][b]=pre[a-1][b];
				if(b-m-1>=0) dp[a][b]=mod(dp[a][b]-pre[a-1][b-m-1]+mo);
				if(b>0) pre[a][b]=mod(pre[a][b-1]+dp[a][b]);
				else pre[a][b]=dp[a][b];
	      	}
       	}
       	int ans=ksm(m+1,2*n,mo);
      //	cout<<ans<<endl;
       	for(int a=0;a<=n*m;a++) ans=mod(ans-(ll)dp[n][a]*dp[n][a]%mo+mo);
       	printf("%lld\n",(ll)ans*ny%mo*ksm(ksm(m+1,2*n,mo),mo-2,mo)%mo);
	}
}
